POI2013 Triumphal arch

POI
二分, 贪心

POI2013 Triumphal arch

题目大意：

有一棵树，1号节点已经被染黑，其余是白的。A、B两人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步。如果B能走到A没染的节点，则B获胜，否则若A染完全部的n个节点，则A获胜。求A能获胜的最小的k。

$PS.$ 比较显然的贪心。

题解：

首先二分答案是很显然的，关键在于判定A能否获胜。

我是直接贪心来写的。

有一个很明显的思路：B在点i时，轮到B走，B的所有儿子都必须已经被染过，否则下一步A就会输。

那么定义sum[i]表示B在点i时，A染完i的所有儿子后，还剩下的染点个数。

若$sum[i]<0$表示单凭这一次染色无法染完i的儿子，那么这时候，我们就需要用i的祖先中$sum[i]>0$的那些点留出来的染色机会来协助i的染色。

于是我们从叶子节点往根一层一层遍历，如果当前节点染色次数不足，则向父亲要。(若父亲不够，则在遍历到它时，它又会向它的父亲要。)

最后，到根节点为止，根节点没有父亲因而无法向上要，因而我们就看根此时能否满足即可。

总的复杂度为$O(nlogn)$ 。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=300005;
int head[N],tot_edge;
struct Edge{
	int to,nxt;
}edge[N<<1];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
int n,cnt[N],fa[N];
ll sum[N];
vector<int>num[N];
void dfs(int p,int f,int d){
	num[d].push_back(p);
	fa[p]=f;
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to!=f)dfs(to,p,d+1);
	}
}
bool judge(int mid){
	if(mid<cnt[1])return false;
	memset(sum,0,sizeof(sum));
	sum[1]=mid-cnt[1];
	for(int d=1;d<=n;d++){
		for(int i=0;i<num[d].size();i++){
			int p=num[d][i];
			int par=fa[p];
			sum[p]=mid-cnt[p]+1;
		}
	}
	for(int d=n;d>=1;d--){
		for(int i=0;i<num[d].size();i++){
			int p=num[d][i];
			int par=fa[p];
			if(sum[p]<0){
				sum[par]+=sum[p];
			}
		}
	}
	if(sum[1]<0)return false;
	return true;
}
int main(){
	memset(head,-1,sizeof(head));
	Rd(n);
	for(int i=1,a,b;i<n;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);
		cnt[a]++,cnt[b]++;
	}
	dfs(1,0,0);
	int L=0,R=n,res=-1;
	while(L<=R){
		int mid=L+R>>1;
		if(judge(mid)){
			res=mid;
			R=mid-1;
		}else L=mid+1;
	}
	printf("%d\n",res);
	return 0;
}
分享到 评论